/*
 * Copyright (c) 2012 Johan Fylling
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy 
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights 
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 
 * copies of the Software, and to permit persons to whom the Software is 
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in 
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 
 * THE SOFTWARE.
 */

part of tools;


/**
 * [Iterator] for [SmartSet].
 */
class SmartIterator<E> implements Iterator<E> {
  SmartLink<E> _element = null;
  E            _current = null;
  
  SmartIterator (SmartLink<E> element) : this._element = element;
  
  bool get hasNext  => this._element != null && this._element._next != null;
  
  bool moveNext () {
    if (this._element != null) {
      if (this._current != null) {
        this._element = this._element._next;
      }
      if (this._element != null) {
        this._current = this._element._data;
        return true;
      }
    }
    return false;
  }
  
  E get current => this._current;
}


/**
 * To justify use of [SmartSet], objects put in such collections should extend [SmartElement].
 */
class SmartElement {
  final Map<int, SmartLink> _links;
  
  SmartElement () : this._links = new Map<int, SmartLink>();
  
  /** Returns [true], if this [SmartElement] is a member of the [SmartSet] */
  bool isMemberOf (SmartSet ss) => this._links.containsKey(ss._id);
  
  void _addTo (SmartSet ss, SmartLink sl) {
    this._links[ss._id] = sl;
  }
  
  /** Removes this [SmartElement] from the provided [SmartSet]. */
  bool removeFrom (SmartSet ss) {
    SmartLink sl = this._links.remove(ss._id);
    if (sl != null) {
      return sl.removeFrom(ss);
    }
    return false;
  }
}


/**
 * Link used in [SmartSet].
 */
class SmartLink<E> {
  E            _data    = null;
  SmartLink<E> _next    = null;
  SmartLink<E> _prev    = null;
  final int    _owner;
  
  SmartLink (int owner) : _owner = owner;
  
  /** The pointers to adjacent links are maintained after removal. */
  bool removeFrom (SmartSet ss) {
    if (this._owner == ss._id) {
      SmartLink prev = this._prev;
      SmartLink next = this._next;
      if (ss._first == this) {
        ss._first = this._next;
      } else if (prev != null){
        prev._next = next;
      }
      if (ss._last == this) {
        ss._last = this._prev;
      } else if (next != null) {
        next._prev = prev;
      }
      return true;
    }
    return false;
  }
}


/**
 * Set implemented as a doubly linked list.
 * The [SmartSet] takes arbitrary types, and in such case works as an ordinary set.
 * Types extending [SmartElement] receives special treatment. Such objects are faster to remove and
 * has faster containment checks. 
 */
class SmartSet<E> implements Set<E> {
  static int   _idCounter = 0;
  final int    _id        = _idCounter++;
  SmartLink<E> _first     = null;
  SmartLink<E> _last      = null;
  
  /** See [Collection.first] */
  E get first {
    if (this._first != null) {
      if (this._first._data != null) {
        return this._first._data;
      }
      throw new StateError("SmartSet [$_id] has a first element, but it contains no data.");
    }
    throw new StateError("SmartSet [$_id] has no first element.");
  }
  
  /** See [Collection.isEmpty] */
  bool get isEmpty {
    return this._first == null && this._last == null;
  }
  
  /** See [Iterable.iterator]. */
  Iterator<E> get iterator => new SmartIterator<E>(this._first);
  
  /** See [Collection.last] */
  E get last {
    if (this._last != null) {
      if (this._last._data != null) {
        return this._last._data;
      }
      throw new StateError("SmartSet [$_id] has a last element, but it contains no data.");
    }
    throw new StateError("SmartSet [$_id] has no last element.");
  }
  
  /** 
   * This is a slow operation, as the length is not tracked internally; instead 
   * each element is iterated over to be counted.
   * 
   * See [Collection.get length].
   */
  int get length {
    int l = 0;
    forEach((E e) => l++);
    return l;
  }
  
  /** See [Set.single]. */
  E get single {
    int length = this.length;
    if (length == 1) {
      return this.first;
    }
    throw new StateError("SmartSet [$_id] has $length elements.");
  }
  
  /** See [Set.add]. */
  void add (E value) {
    if (contains(value)) {
      return;
    }
    
    SmartLink<E> link = new SmartLink<E>(this._id);
    link._data = value;
    
    if (value is SmartElement) {
      (value as SmartElement)._addTo(this, link);
    }
    
    if (this._first == null) {
      this._first = link;
    }
    if (this._last == null) {
      this._last = link;
    } else {
      this._last._next = link;
      link._prev = this._last;
      this._last = link;
    }
  }
  
  /** See [Set.addAll]. */
  void addAll (Collection<E> collection) {
    if (collection != null) {
      for (E value in collection) {
        add(value);
      }
    }
  }
  
  /** See [Iterable.any]. */
  bool any (bool f(E element)) {
    for (E e in this) {
      if (f(e)) {
        return true;
      }
    }
    return false;
  }
  
  /** See [Set.clear]. */
  void clear () {
    while (this._first != null) {
      this._first.removeFrom(this);
    }
  }
  
  /** 
   * See [Set.contains].
   * 
   * If [value] is of type [SmartElement], the effort is relative to the number
   * of sets [value] is a member of, not the size of this [SmartSet].
   */
  bool contains (E value) {
    if (value == null) {
      return false;
    }
    
    if (value is SmartElement) {
      return (value as SmartElement).isMemberOf(this);
    } else {
      for (E e in this) {
        if (value == e) {
          return true;
        }
      }
    }
    return false;
  }
  
  /** See [Set.containsAll]. */
  bool containsAll (Collection<E> collection) {
    for (E value in collection) {
      if (!contains(value)) {
        return false;
      }
    }
    return true;
  }
  
  /** See [Iterable.elementAt]. */
  E elementAt (int index) {
    int counter = 0;
    for (E e in this) {
      if (counter == index) {
        return e;
      }
      ++counter;
    }
    throw new RangeError.value(index);
  }
  
  /** See [Iterable.every]. */
  bool every (bool f(E element)) {
    for (E e in this) {
      if (!f(e)) {
        return false;
      }
    }
    return true;
  }
  
  /** Does nothing. **/
  Iterable expand (Iterable f(E element)) {
  }
  
  /** See [Iterable.firstMatching]. */
  E firstMatching (bool test(E element), {E orElse()}) {
    for (E e in this) {
      if (test(e)) {
        return e;
      }
    }
    if (orElse != null) {
      return orElse();
    }
    throw new StateError("Found no match in SmartSet [$_id].");
  }
  
  /** See [Iterable.forEach]. **/
  void forEach (void f(E element)) {
    for (E e in this) {
      f(e);
    }
  }
  
  /** See [Set.intersection]. */
  Set<E> intersection (Collection<E> collection) {
    SmartSet<E> ss = new SmartSet<E>();
    for (E value in collection) {
      if (contains(value)) {
        ss.add(value);
      }
    }
    return ss;
  }
  
  /** See [Set.isSubsetOf]. */
  bool isSubsetOf (Collection<E> collection) {
    for (E value in this) {
      bool found = false;
      for (E otherValue in collection) {
        if (value == otherValue) {
          found = true;
          break;
        }
      }
      if (!found) {
        return false;
      }
    }
    return true;
  }
  
  /** See [Iterable.join]. */
  String join ([String separator]) {
    StringBuffer buffer = new StringBuffer();
    bool firstPass = true;
    for (E e in this) {
      if (firstPass) {
        firstPass = false;
      } else {
        buffer.add(separator);
      }
      buffer.add(e);
    }
    return buffer.toString();
  }
  
  /** See [Iterable.lastMatching]. */
  E lastMatching (bool test(E element), {E orElse()}) {
    E match = null;
    for (E e in this) {
      if (test(e)) {
        match = e;
      }
    }
    if (match != null) {
      return match;
    }
    if (orElse != null) {
      return orElse();
    }
    throw new StateError("Found no match in SmartSet [$_id].");
  }
  
  /** 
   * See [Iterable.map].
   * Not lazy.
   **/
  // TODO: Make lazy.
  Iterable map (f(E element)) {
    SmartSet ss = new SmartSet();
    for (E e in this) {
      ss.add(f(e));
    }
    return ss;
  }
  
  /** See [Iterable.max]. */
  E max ([int compare(E a, E b)]) {
    for (E e1 in this) {
      bool largest = false;
      for (E e2 in this) {
        if (compare(e1, e2) >= 0) {
          largest = true;
        }
      }
      if (largest) {
        return e1;
      }
    }
    return null;
  }
  
  /** See [Iterable.min]. */
  E min ([int compare(E a, E b)]) {
    for (E e1 in this) {
      bool smallest = false;
      for (E e2 in this) {
        if (compare(e1, e2) <= 0) {
          smallest = true;
        }
      }
      if (smallest) {
        return e1;
      }
    }
    return null;
  }
  
  /** 
   * See [Iterable.reduce].
   * 
   * Note: This is an odd one ...
   */
  reduce (initialValue, combine(previousValue, E element)) {
    forEach((E e) {
      initialValue = combine(initialValue, e);
    });
    clear();
    add(initialValue);
  }
  
  /**
   * See [Set.remove].
   * 
   * If [value] is of type [SmartElement], the effort is relative to the number
   * of sets [value] is a member of, not the size of this [SmartSet].
   */
  bool remove (E value) {
    if (value == null) {
      return false;
    }
    
    if (value is SmartElement && contains(value)) {
      return (value as SmartElement).removeFrom(this);
    }
    
    SmartLink<E> element = this._first;
    while (element != null) {
      if (element._data == value) {
        return element.removeFrom(this);
      }
      element = element._next;
    }
    return false;
  }
  
  /** See [Collection.removeAll]. */
  void removeAll (Iterable elements) {
    for (E e in elements) {
      remove(e);
    }
  }
  
  /** See [Collection.removeMatching]. */
  void removeMatching (bool test(E element)) {
    for (E e in this) {
      if (test(e)) {
        remove(e);
      }
    }
  }
  
  /** See [Collection.retainAll]. */
  void retainAll (Iterable elements) {
    for (E e in this) {
      if (!elements.contains(e)) {
        remove(e);
      }
    }
  }
  
  /** See [Collection.retainMatching]. */
  void retainMatching (bool test(E element)) {
    for (E e in this) {
      if (!test(e)) {
        remove(e);
      }
    }
  }
  
  /** See [Collection.singleMatching]. */
  E singleMatching (bool test(E element)) {
    E match = null;
    for (E e in this) {
      if (test(e)) {
        if (match != null) {
          throw new StateError("Found more than one match in SmartSet [$_id].");
        }
        match = e;
      }
    }
    if (match != null) {
      return match;
    }
    throw new StateError("Found no match in SmartSet [$_id].");
  }
  
  /** See [Iterable.skip]. */
  Iterable<E> skip (int n) {
    SmartSet<E> set = new SmartSet<E>();
    for (E e in this) {
      if (n > 0) {
        n--;
      } else {
        set.add(e);
      }
    }
    return set;
  }
  
  /** See [Iterable.skipWhile]. */
  Iterable<E> skipWhile (bool test(E value)) {
    SmartSet<E> set = new SmartSet<E>();
    bool add = false;
    for (E e in this) {
      if (add || !test(e)) {
        add = true;
        set.add(e);
      }
    }
    return set;
  }
  
  /** See [Iterable.take]. */
  Iterable<E> take (int n) {
    SmartSet<E> set = new SmartSet<E>();
    for (E e in this) {
      if (n <= 0) {
        return set;
      }
      set.add(e);
      n--;
    }
    return set;
  }
  
  /** See [Iterable.takeWhile]. */
  Iterable<E> takeWhile (bool test(E value)) {
    SmartSet<E> set = new SmartSet<E>();
    for (E e in this) {
      if (!test(e)) {
        return set;
      }
      set.add(e);
    }
    return set;
  }
  
  /** See [Iterable.toList]. */
  List<E> toList ({bool growable: true}) {
    List<E> list = new List<E>();
    for (E e in this) {
      list.add(e);
    }
    return list;
  }
  
  /** See [Iterable.toSet]. */
  Set<E> toSet () {
    Set<E> set = new Set<E>();
    for (E e in this) {
      set.add(e);
    }
    return set;
  }
  
  /** 
   * See [Iterable.where]. 
   * Not lazy.
   **/
  // TODO: Make lazy.
  Iterable<E> where (bool f(E element)) {
    SmartSet<E> set = new SmartSet<E>();
    for (E e in this) {
      if (f(e)) {
        set.add(e);
      }
    }
    return set;
  }
  
  String toString () {
    return "[${join(",")}]";
  }
}
